1. Agrégation externe de mathématiques

1.1 Leçon orale, option informatique

Feedbacks?


2. Calcul du plus long sous mot commun

2.0.1 Implémentation d'un développement pour les leçons 906, 907.

On présente ici un algorithme de programmation dynamique pour le calcul du plus long sous mot commun (attention, c'est différent de la plus longue sous séquence commune !).

Étant donnés deux mots $X = x_1 \dots x_m$ et $Y = y_1 \dots y_n$ sur un alphabet $\Sigma$, on cherche à savoir quel est le plus long sous-mot commun à $X$ et $Y$. Un sous-mot correspond à un morceau commun aux deux mots : on extraie de façon consécutive une sous-séquence de $x$ et $y$ et elles doivent être égales : $u = x_{i_0} \dots x_{i_0 + k} = y_{j_0} \dots y_{j_0 + k} = v$ !

La solution naïve est d’énumérer tous les sous-mots de $X$, et de regarder ensuite s'ils sont aussi sous-mots de $Y$, mais cette solution est inefficace : il y a $\mathcal{O}(2^m)$ sous-mots de X...

L'objectif est donc d'obtenir un algorithme plus efficace, si possible polynomial en $m = |X|$ et $n = |Y|$ (il sera en $\mathcal{O}(m n)$).

2.0.2 Références :

2.0.3 Applications, généralisations :

  • Un généralisation est le calcul de la plus longue sous-sequence commune, pour lequel on ne se restreint plus à extraire de façon consécutive (ca semble plus compliqué, mais le même algorithme permet de régler le problème avec la même complexité, en fait).
  • On peut citer en application la comparaison de chaînes d'ADN, mais aussi la commande diff des systèmes GNU/Linux.
  • Généralisation : aucune chance d'avoir un algorithme aussi efficace s'il s'agit de trouver le plus long sous mot commun à $K$ chaînes de caractères (et en fait, le probleme général est $\mathcal{NP}$, en le nombre de chaînes, comme expliqué ici (en anglais)).

3. Algorithme naïf (exponentiel)

On va d'abord montrer rapidement une implémentation simple de l'algorithme naïf, pour ensuite vérifier que l'algorithme plus complexe fonctionne aussi bien.

3.1 Détecter si $u$ est sous mot de $y$

L'objectif de toutes les fonctions suivantes est de proscrire toute recopie de chaines (slicing, x[i:j]), qui sont très couteuse.


In [1]:
def indiceSousMotAux(u, n, k, y, m, i, delta=0):
    """ Fonction tail-récursive qui trouve l'indice j tel que u[k:k+n] = y[i+j:i+j+n], ou -1 en cas d'échec."""
    # print("{}indiceSousMotAux(u = {}, n = {}, k = {}, y = {}, m = {}, i = {}, delta = {})".format('  '*delta, u, n, k, y, m, i, delta))  # DEBUG
    if n == 0:  # Mot vide, commun partout, par defaut on donne 0
        return 0
    else:       # Mot pas vide
        if k >= len(u) or i >= m:  # On a cherché trop loin, échec
            return -1         # -1 signifie échec
        elif u[k] == y[i]:    # Lettre en commun
            if delta == n - 1:    # On a fini, on a trouvé !
                return i - n + 1  # i est l'indice de la derniere lettre ici
            else:  # On continue de chercher, une lettre de moins
                return indiceSousMotAux(u, n, k + 1, y, m, i + 1, delta=delta+1)
        else:      # On recommence a chercher en i+1
            return indiceSousMotAux(u, n, k - delta, y, m, i + 1)


def indiceSousMot(u, y):
    """ En O(|u|), trouve l'indice j tel que u = y[j:j+|u|], ou -1 en cas d'échec."""
    return indiceSousMotAux(u, len(u), 0, y, len(y), 0)


def estSousMot(u, y):
    """ Vérifie en O(|u|) si u est sous-mot de y."""
    return indiceSousMotAux(u, len(u), 0, y, len(y), 0) >= 0

Quelques tests :


In [2]:
def test_estSousMot(u, y):
    """ Teste et affiche. """
    i = indiceSousMot(u, y)
    if i >= 0:
        print("Le mot u = '{}' est sous-mot de y = '{}', a partir de l'indice i = {}.".format(u, y, i))
    else:
        print("Le mot u = '{}' n'est pas sous-mot de y = '{}'.".format(u, y))        


u = "cde"
y1 = "abcdefghijklmnopqrstuvwxyz"
test_estSousMot(u, y1)  # True

y2 = "abcDefghijklmnopqrstuvwxyz"
test_estSousMot(u, y2)  # False


Le mot u = 'cde' est sous-mot de y = 'abcdefghijklmnopqrstuvwxyz', a partir de l'indice i = 2.
Le mot u = 'cde' n'est pas sous-mot de y = 'abcDefghijklmnopqrstuvwxyz'.

3.2 Trouver un sous-mot de longueur k

On peut chercher tous les sous-mots de longueur k dans x et regarder si l'un d'entre eux est inclus dans y (on s'arrête dès qu'on en a trouvé un) :


In [3]:
def aSousMotDeLongueur(x, y, k):
    """ Trouve le premier sous-mot de x de longueur k et renvoit i, j, u, ou échoue avec une ValueError. """
    imax = len(x) - k + 1
    # Les sous mots seront x0..xk-1, .., ximax-1,..,xn-1
    for debut in range(imax):
        j = indiceSousMotAux(x, k, debut, y, len(y), 0)
        if j >= 0:
            return debut, debut + j, x[debut:debut+k]
    # Pas trouvé !
    raise ValueError("Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.".format(k, x, y))

Un test :


In [4]:
def test_aSousMotDeLongueur(x, y, k):
    """ Teste et affiche. """
    try:
        i, j, u = aSousMotDeLongueur(x, y, k)
        print("==> Sous-mot de longueur k = {} de x = '{}' dans y = '{}' : u = '{}' en indice i = {} pour x et j = {} pour y.".format(k, x, y, u, i, j))
    except ValueError:
        print("==> Aucun sous-mot de longueur k = {} de x = '{}' n'est dans y = '{}'.".format(k, x, y))

x = "aabcde"
y = "aABcdE"
for k in range(0, min(len(x), len(y)) + 1):
    test_aSousMotDeLongueur(x, y, k)

x = "aabffcde"
y = "aABGGGGGcdE"
for k in range(0, min(len(x), len(y)) + 1):
    test_aSousMotDeLongueur(x, y, k)


==> Sous-mot de longueur k = 0 de x = 'aabcde' dans y = 'aABcdE' : u = '' en indice i = 0 pour x et j = 0 pour y.
==> Sous-mot de longueur k = 1 de x = 'aabcde' dans y = 'aABcdE' : u = 'a' en indice i = 0 pour x et j = 0 pour y.
==> Sous-mot de longueur k = 2 de x = 'aabcde' dans y = 'aABcdE' : u = 'cd' en indice i = 3 pour x et j = 6 pour y.
==> Aucun sous-mot de longueur k = 3 de x = 'aabcde' n'est dans y = 'aABcdE'.
==> Aucun sous-mot de longueur k = 4 de x = 'aabcde' n'est dans y = 'aABcdE'.
==> Aucun sous-mot de longueur k = 5 de x = 'aabcde' n'est dans y = 'aABcdE'.
==> Aucun sous-mot de longueur k = 6 de x = 'aabcde' n'est dans y = 'aABcdE'.
==> Sous-mot de longueur k = 0 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = '' en indice i = 0 pour x et j = 0 pour y.
==> Sous-mot de longueur k = 1 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = 'a' en indice i = 0 pour x et j = 0 pour y.
==> Sous-mot de longueur k = 2 de x = 'aabffcde' dans y = 'aABGGGGGcdE' : u = 'cd' en indice i = 5 pour x et j = 13 pour y.
==> Aucun sous-mot de longueur k = 3 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.
==> Aucun sous-mot de longueur k = 4 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.
==> Aucun sous-mot de longueur k = 5 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.
==> Aucun sous-mot de longueur k = 6 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.
==> Aucun sous-mot de longueur k = 7 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.
==> Aucun sous-mot de longueur k = 8 de x = 'aabffcde' n'est dans y = 'aABGGGGGcdE'.

3.3 Sous-mot de longueur maximale (version naïve)


In [5]:
def _sousMotMax(x, y, verb=True):
    """ |x| doit etre plus petit que |y|."""
    k = len(x)
    while k >= 0:
        if verb:
            print("  On essaie de trouver un sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...".format(x, y, k))
        try:
            i, j, u = aSousMotDeLongueur(x, y, k)
            if verb:
                print("  ==> On a un sous-mot commun à x = '{}' et y = '{}' de taille k = {} : u = '{}' (i = {}, j = {}) !".format(x, y, k, u, i, j))
            return i, j, u
        except ValueError:
            if verb:
                print("  ==> Aucun sous-mot commun à x = '{}' et y = '{}' de taille k = {} ...".format(x, y, k))
        k -= 1

            
def sousMotMax(x, y, verb=True):
    """ Trouve un sous-mot de longueur maximale (le plus à gauche possible de x et y), en temps exponentiel en n = |x|."""
    if len(x) <= len(y):
        return _sousMotMax(x, y, verb=verb)
    else:
        return _sousMotMax(y, x, verb=verb)

Quelques tests :


In [6]:
x = "abcABCabc123456abcABCabc99"
y = "abcDEFdef123456abcDEFdef9999"
sousMotMax(x, y, verb=False)


Out[6]:
(9, 18, '123456abc')

In [7]:
x = "abcABCabc"
y = "abcDEFdef"
sousMotMax(x, y)


  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ...
  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 9 ...
  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ...
  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 8 ...
  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ...
  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 7 ...
  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ...
  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 6 ...
  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ...
  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 5 ...
  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ...
  ==> Aucun sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 4 ...
  On essaie de trouver un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 ...
  ==> On a un sous-mot commun à x = 'abcABCabc' et y = 'abcDEFdef' de taille k = 3 : u = 'abc' (i = 0, j = 0) !
Out[7]:
(0, 0, 'abc')

4. Méthode gloutonne (programmation dynamique)

On passe désormais à la seconde approche, qui sera bien plus efficace (et qui montrera que le probleme du plus long sous-mot commun de deux mots est dans $\mathcal{P}$).

Cette approche a l'avantage d'être bien plus efficace, mais aussi plus simple à coder. On a juste besoin d'une matrice de taille $(|x|+1)(|y|+1)$ (un numpy.array, pour être plus efficace qu'une liste de liste), et quelques boucles for.


In [8]:
# On a besoin du module numpy. Cf. http://numpy.org/ pour l'installer si besoin
import numpy as np

4.1 Programmation dynamique, sans optimisation mémoire

La fonction ci-dessous procède en 4 étapes :

  1. Initialisation de la matrice longueurs, pleine de $0$ et de taille $(n+1) \times (m+1)$ où $y := |x|$ et $m := |y|$,
  2. Calcul "bottom-up" de la matrice longueurs, par l'équation suivante : $$ \mathrm{longueurs}[i, j] = 1 + \mathrm{longueurs}[i-1, j-1] \; \text{si} \; x[i-1] = y[i-1]. $$
  3. Calcul de la longueur maximale d'une correspondance entre x et y, par un simple parcours (longueur_max), et calcul des indices de début de cette coresspondance maximale (= plus long sous-mot !), idebut et jdebut.
  4. (optionnel) On vérifie que x[idebut : idebut + longueur_max] = y[jdebut : jdebut + longueur_max].

On commence en utilisant une matrice, pleine de $0$ (ie. une matrice nulle). Comme on va le voir dans les exemples ci-dessous, en pratique cette matrice restera presque "vide", consommant beaucoup de memoire ($\mathcal{O}(n m)$) inutilement. La version suivante sera optimisée (en utilisant une matrice sparse, ie. creuse).

Cet algorithme sera en :

  • $\mathcal{O}(n m)$ en mémoire, dans tous les cas (mais on peut faire mieux),
  • $\mathcal{O}(n m)$ en temps, dans tous les cas (et on ne peut pas faire mieux).


In [9]:
def sousMotMaxGlouton(x, y, verb=False, verifie=True):
    """ Calcule le plus long sous-mot commun a x et y, par programmation dynamique.
    
        - affiche un peu ce qu'il se passe si verb=True,
        - vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.
    """
    def message(*args):
        if verb:
            print(*args) 
    # 1. et 2. Initialisation et construction Matrice longueurs
    n = len(x)
    m = len(y)
    message("\n1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = {} m = {} ...".format(n, m))
    longueurs = np.zeros((n+1, m+1), dtype=int)
    message("2. Construction bottom-up de la loop-up matrice longueurs ...")
    for i in range(1, n+1):
        for j in range(1, m+1):
            if x[i-1] == y[j-1]:
                longueurs[i, j] = 1 + longueurs[i-1, j-1]
                message("      Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))
    # 3. Utilisation de la matrice longueurs
    iFin, jFin = 0, 0
    longueur_max = -1  # Pas encore
    message("3. Calcul de la position du plus long sous mot via la matrice longueurs ...")
    for i in range(0, n+1):
        for j in range(0, m+1):
            if longueur_max < longueurs[i, j]:
                longueur_max = longueurs[i, j]
                iFin, jFin = i, j
    # Note : avec les fonctions numpy np.max et np.argmax on pourrait faire ça plus vite (pour des matrices) :
    # longueur_max = np.max(longueurs)
    # iFin, jFin = np.unravel_index(np.argmax(longueurs), np.shape(longueurs))
    # Calcul des indices de debut
    iDebut, jDebut = iFin - longueur_max, jFin - longueur_max
    message("4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...".format(iDebut, jDebut, longueur_max))

    # 4. Vérification
    if verifie:
        xSous = x[iDebut: iDebut + longueur_max]
        ySous = y[jDebut: jDebut + longueur_max]
        message("      Sous-mot dans x = {}, et sous-mot dans y = {} ...".format(xSous, ySous))
        assert xSous == ySous, "Erreur, xSous et ySous sont différents !"
    
    leSousMot = x[iDebut: iDebut + longueur_max]
    return iDebut, jDebut, leSousMot, longueurs

On peut faire quelques tests, comme pour l'approche initiale.


In [10]:
x = "BDCABA"
y = "ABCBDAB"
sousMotMaxGlouton(x, y, verb=True)


1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 6 m = 7 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
      Correspondance en cours, u[0] = B et v[1] = B, de longueur courante 1 ...
      Correspondance en cours, u[0] = B et v[3] = B, de longueur courante 1 ...
      Correspondance en cours, u[0] = B et v[6] = B, de longueur courante 1 ...
      Correspondance en cours, u[1] = D et v[4] = D, de longueur courante 2 ...
      Correspondance en cours, u[2] = C et v[2] = C, de longueur courante 1 ...
      Correspondance en cours, u[3] = A et v[0] = A, de longueur courante 1 ...
      Correspondance en cours, u[3] = A et v[5] = A, de longueur courante 1 ...
      Correspondance en cours, u[4] = B et v[1] = B, de longueur courante 2 ...
      Correspondance en cours, u[4] = B et v[3] = B, de longueur courante 1 ...
      Correspondance en cours, u[4] = B et v[6] = B, de longueur courante 2 ...
      Correspondance en cours, u[5] = A et v[0] = A, de longueur courante 1 ...
      Correspondance en cours, u[5] = A et v[5] = A, de longueur courante 1 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 0 et jDebut = 3 et longueur_max = 2 ...
      Sous-mot dans x = BD, et sous-mot dans y = BD ...
Out[10]:
(0, 3, 'BD', array([[0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0, 1],
        [0, 0, 0, 0, 0, 2, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 1, 0],
        [0, 0, 2, 0, 1, 0, 0, 2],
        [0, 1, 0, 0, 0, 0, 1, 0]]))

In [11]:
x = "abcABCabc123456abcABCabc99"
y = "abcDEFdef123456abcDEFdef9999"
sousMotMaxGlouton(x, y, verb=True)


1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 26 m = 28 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
      Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[0] = a et v[15] = a, de longueur courante 1 ...
      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[1] = b et v[16] = b, de longueur courante 2 ...
      Correspondance en cours, u[2] = c et v[2] = c, de longueur courante 3 ...
      Correspondance en cours, u[2] = c et v[17] = c, de longueur courante 3 ...
      Correspondance en cours, u[6] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[6] = a et v[15] = a, de longueur courante 1 ...
      Correspondance en cours, u[7] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[7] = b et v[16] = b, de longueur courante 2 ...
      Correspondance en cours, u[8] = c et v[2] = c, de longueur courante 3 ...
      Correspondance en cours, u[8] = c et v[17] = c, de longueur courante 3 ...
      Correspondance en cours, u[9] = 1 et v[9] = 1, de longueur courante 1 ...
      Correspondance en cours, u[10] = 2 et v[10] = 2, de longueur courante 2 ...
      Correspondance en cours, u[11] = 3 et v[11] = 3, de longueur courante 3 ...
      Correspondance en cours, u[12] = 4 et v[12] = 4, de longueur courante 4 ...
      Correspondance en cours, u[13] = 5 et v[13] = 5, de longueur courante 5 ...
      Correspondance en cours, u[14] = 6 et v[14] = 6, de longueur courante 6 ...
      Correspondance en cours, u[15] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[15] = a et v[15] = a, de longueur courante 7 ...
      Correspondance en cours, u[16] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[16] = b et v[16] = b, de longueur courante 8 ...
      Correspondance en cours, u[17] = c et v[2] = c, de longueur courante 3 ...
      Correspondance en cours, u[17] = c et v[17] = c, de longueur courante 9 ...
      Correspondance en cours, u[21] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[21] = a et v[15] = a, de longueur courante 1 ...
      Correspondance en cours, u[22] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[22] = b et v[16] = b, de longueur courante 2 ...
      Correspondance en cours, u[23] = c et v[2] = c, de longueur courante 3 ...
      Correspondance en cours, u[23] = c et v[17] = c, de longueur courante 3 ...
      Correspondance en cours, u[24] = 9 et v[24] = 9, de longueur courante 1 ...
      Correspondance en cours, u[24] = 9 et v[25] = 9, de longueur courante 1 ...
      Correspondance en cours, u[24] = 9 et v[26] = 9, de longueur courante 1 ...
      Correspondance en cours, u[24] = 9 et v[27] = 9, de longueur courante 1 ...
      Correspondance en cours, u[25] = 9 et v[24] = 9, de longueur courante 1 ...
      Correspondance en cours, u[25] = 9 et v[25] = 9, de longueur courante 2 ...
      Correspondance en cours, u[25] = 9 et v[26] = 9, de longueur courante 2 ...
      Correspondance en cours, u[25] = 9 et v[27] = 9, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 9 et jDebut = 9 et longueur_max = 9 ...
      Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...
Out[11]:
(9,
 9,
 '123456abc',
 array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0,
         0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 1, 1, 1, 1],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
         0, 0, 0, 1, 2, 2, 2]]))

On commence à constater que la matrice longueurs est toujours presque remplie de zéros, même après tous les calculs ! Peut-être qu'on peut faire mieux, niveau espace de stockage (complexité en mémoire), pour éviter de stocker un nombre trop grand de zéros inutiles. Une version améliorée est présentée ci-dessous, on parvient à diminuer grandement la complexité (moyenne) en mémoire en utilisant une structure intelligente de matrice "creuse".


In [12]:
x = "abcZZdeFG597"
y = "AbCdEFG413ZAQCWQ"
sousMotMaxGlouton(x, y, verb=True)


1. Initialisation de la look-up matrice longueurs de taille (n+1, m+1) : n = 12 m = 16 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...
      Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...
      Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...
      Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...
      Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...
      Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...
      Sous-mot dans x = FG, et sous-mot dans y = FG ...
Out[12]:
(7, 5, 'FG', array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]))

4.2 Utilisation d'une matrice creuse

On va utiliser le module scipy.sparse pour utiliser un codage efficace pour cette matrice longueurs : un codage dit creux qui permettra de ne pas stocker tous ces zéros inutiles.


In [13]:
from scipy.sparse import lil_matrix

On utilise la structure lil_matrix (lil pour "LInked List"), car c'est la plus efficace quant la matrice change de structure sparse (on rajoute des valeurs non-nulles au fur et à mesure de sa construction).

Exemple :


In [14]:
print("I_12 pleine :\n", np.eye(12))
I12 = lil_matrix(np.eye(12))
print("I_12 creuse :\n", I12)
I12


I_12 pleine :
 [[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]]
I_12 creuse :
   (0, 0)	1.0
  (1, 1)	1.0
  (2, 2)	1.0
  (3, 3)	1.0
  (4, 4)	1.0
  (5, 5)	1.0
  (6, 6)	1.0
  (7, 7)	1.0
  (8, 8)	1.0
  (9, 9)	1.0
  (10, 10)	1.0
  (11, 11)	1.0
Out[14]:
<12x12 sparse matrix of type '<class 'numpy.float64'>'
	with 12 stored elements in LInked List format>

In [15]:
print("Taille de I_12 creuse =", I12.size)


Taille de I_12 creuse = 12

On peut prendre exactement la même fonction, et changer la ligne qui crée la matrice longueurs : on ajoute un appel à lil_matrix pour en faire une matrice creuse.

Et voilà comment on passe, en une ligne, de $\mathcal{O}(n m)$ en mémoire dans tous les cas à un $\mathcal{O}(n m)$ dans le pire des cas et $\mathcal{O}(\sum \text{longueur des sous-mots de x et y})$ dans tous les cas (en moyenne, ce sera $\mathcal{O}(\min(n, m))$ au pire). Notez que ce sera un poil moins efficace, mais on garde la complexité en temps en $\mathcal{O}(n m)$ de toute façon.


In [16]:
def sousMotMaxGloutonCreux(x, y, verb=False, verifie=True):
    """ Calcule le plus long sous-mot commun a x et y, par programmation dynamique.
    
        - affiche un peu ce qu'il se passe si verb=True,
        - vérifie que le sous-mot commun est bien un bon sous-mot commun si verifie=True.
    """
    def message(*args):
        if verb:
            print(*args) 
    # 1. et 2. Initialisation et construction Matrice longueurs
    n = len(x)
    m = len(y)
    message("\n1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = {} m = {} ...".format(n, m))
    longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))
    message("2. Construction bottom-up de la loop-up matrice longueurs ...")
    for i in range(1, n+1):
        for j in range(1, m+1):
            if x[i-1] == y[j-1]:
                longueurs[i, j] = 1 + longueurs[i-1, j-1]
                message("      Correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))
    # 3. Utilisation de la matrice longueurs
    iFin, jFin = 0, 0
    longueur_max = -1  # Pas encore
    message("3. Calcul de la position du plus long sous mot via la matrice longueurs ...")
    for i in range(0, n+1):
        for j in range(0, m+1):
            if longueur_max < longueurs[i, j]:
                longueur_max = longueurs[i, j]
                iFin, jFin = i, j
    # Calcul des indices de debut
    iDebut, jDebut = iFin - longueur_max, jFin - longueur_max
    message("4. On a obtenu iDebut = {} et jDebut = {} et longueur_max = {} ...".format(iDebut, jDebut, longueur_max))

    # 4. Vérification
    if verifie:
        xSous = x[iDebut: iDebut + longueur_max]
        ySous = y[jDebut: jDebut + longueur_max]
        message("      Sous-mot dans x = {}, et sous-mot dans y = {} ...".format(xSous, ySous))
        assert xSous == ySous, "Erreur, xSous et ySous sont différents !"
    
    leSousMot = x[iDebut: iDebut + longueur_max]
    return iDebut, jDebut, leSousMot, longueurs

On peut faire quelques exemples en plus, et on calcule aussi la taille de la matrice creuse longueurs (pour comparer a la taille de la matrice pleine de la fonction d'avant) :


In [17]:
x = "ab0cABC0abc123456abcABCabc99"
y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)


1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 28 m = 38 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
      Correspondance en cours, u[0] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[0] = a et v[25] = a, de longueur courante 1 ...
      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[1] = b et v[26] = b, de longueur courante 2 ...
      Correspondance en cours, u[2] = 0 et v[12] = 0, de longueur courante 1 ...
      Correspondance en cours, u[2] = 0 et v[16] = 0, de longueur courante 1 ...
      Correspondance en cours, u[3] = c et v[10] = c, de longueur courante 1 ...
      Correspondance en cours, u[3] = c et v[27] = c, de longueur courante 1 ...
      Correspondance en cours, u[6] = C et v[5] = C, de longueur courante 1 ...
      Correspondance en cours, u[7] = 0 et v[12] = 0, de longueur courante 1 ...
      Correspondance en cours, u[7] = 0 et v[16] = 0, de longueur courante 1 ...
      Correspondance en cours, u[8] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[8] = a et v[25] = a, de longueur courante 1 ...
      Correspondance en cours, u[9] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[9] = b et v[26] = b, de longueur courante 2 ...
      Correspondance en cours, u[10] = c et v[10] = c, de longueur courante 1 ...
      Correspondance en cours, u[10] = c et v[27] = c, de longueur courante 3 ...
      Correspondance en cours, u[11] = 1 et v[19] = 1, de longueur courante 1 ...
      Correspondance en cours, u[12] = 2 et v[20] = 2, de longueur courante 2 ...
      Correspondance en cours, u[13] = 3 et v[21] = 3, de longueur courante 3 ...
      Correspondance en cours, u[14] = 4 et v[22] = 4, de longueur courante 4 ...
      Correspondance en cours, u[15] = 5 et v[23] = 5, de longueur courante 5 ...
      Correspondance en cours, u[16] = 6 et v[24] = 6, de longueur courante 6 ...
      Correspondance en cours, u[17] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[17] = a et v[25] = a, de longueur courante 7 ...
      Correspondance en cours, u[18] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[18] = b et v[26] = b, de longueur courante 8 ...
      Correspondance en cours, u[19] = c et v[10] = c, de longueur courante 1 ...
      Correspondance en cours, u[19] = c et v[27] = c, de longueur courante 9 ...
      Correspondance en cours, u[22] = C et v[5] = C, de longueur courante 1 ...
      Correspondance en cours, u[23] = a et v[0] = a, de longueur courante 1 ...
      Correspondance en cours, u[23] = a et v[25] = a, de longueur courante 1 ...
      Correspondance en cours, u[24] = b et v[1] = b, de longueur courante 2 ...
      Correspondance en cours, u[24] = b et v[26] = b, de longueur courante 2 ...
      Correspondance en cours, u[25] = c et v[10] = c, de longueur courante 1 ...
      Correspondance en cours, u[25] = c et v[27] = c, de longueur courante 3 ...
      Correspondance en cours, u[26] = 9 et v[34] = 9, de longueur courante 1 ...
      Correspondance en cours, u[26] = 9 et v[35] = 9, de longueur courante 1 ...
      Correspondance en cours, u[26] = 9 et v[36] = 9, de longueur courante 1 ...
      Correspondance en cours, u[26] = 9 et v[37] = 9, de longueur courante 1 ...
      Correspondance en cours, u[27] = 9 et v[34] = 9, de longueur courante 1 ...
      Correspondance en cours, u[27] = 9 et v[35] = 9, de longueur courante 2 ...
      Correspondance en cours, u[27] = 9 et v[36] = 9, de longueur courante 2 ...
      Correspondance en cours, u[27] = 9 et v[37] = 9, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 11 et jDebut = 19 et longueur_max = 9 ...
      Sous-mot dans x = 123456abc, et sous-mot dans y = 123456abc ...
Taille de la matrice pleine = (n+1)(m+1) = 1131
Taille de la matrice creuse longueurs = 44

Ici, sur deux mots de tailles raisonnables (x = "ab0cABC0abc123456abcABCabc99" et y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999"), on passe d'une matrice pleine de taille 1131 entiers à une matrice creuse de taille 44 entiers : le gain est considérable !


In [18]:
x = "abcZZdeFG597"
y = "AbCdEFG413ZAQCWQ"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=True)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)


1. Initialisation de la look-up matrice longueurs, creuse de taille (n+1, m+1) : n = 12 m = 16 ...
2. Construction bottom-up de la loop-up matrice longueurs ...
      Correspondance en cours, u[1] = b et v[1] = b, de longueur courante 1 ...
      Correspondance en cours, u[3] = Z et v[10] = Z, de longueur courante 1 ...
      Correspondance en cours, u[4] = Z et v[10] = Z, de longueur courante 1 ...
      Correspondance en cours, u[5] = d et v[3] = d, de longueur courante 1 ...
      Correspondance en cours, u[7] = F et v[5] = F, de longueur courante 1 ...
      Correspondance en cours, u[8] = G et v[6] = G, de longueur courante 2 ...
3. Calcul de la position du plus long sous mot via la matrice longueurs ...
4. On a obtenu iDebut = 7 et jDebut = 5 et longueur_max = 2 ...
      Sous-mot dans x = FG, et sous-mot dans y = FG ...
Taille de la matrice pleine = (n+1)(m+1) = 221
Taille de la matrice creuse longueurs = 6

Avec des mots x et y plus longs, le gain en mémoire induit par le codage creux est encore plus impressionnant :


In [19]:
x = "ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù"
y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux(x, y, verb=False)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)


Taille de la matrice pleine = (n+1)(m+1) = 44215
Taille de la matrice creuse longueurs = 1046

4.2.1 Version condensée

Le code de cette fonction sousMotMaxGloutonCreux peut sembler un peu long, mais sans messages ni commentaires il est vraiment court et simple :


In [20]:
def sousMotMaxGloutonCreux2(x, y):
    n = len(x)
    m = len(y)
    
    longueurs = lil_matrix(np.zeros((n+1, m+1), dtype=int))
    for i in range(1, n+1):
        for j in range(1, m+1):
            if x[i-1] == y[j-1]:
                longueurs[i, j] = 1 + longueurs[i-1, j-1]
    
    iFin, jFin = 0, 0
    longueur_max = -1  # Pas encore
    for i in range(0, n+1):
        for j in range(0, m+1):
            if longueur_max < longueurs[i, j]:
                longueur_max = longueurs[i, j]
                iFin, jFin = i, j
    iDebut, jDebut = iFin - longueur_max, jFin - longueur_max

    leSousMot = x[iDebut: iDebut + longueur_max]
    return iDebut, jDebut, leSousMot, longueurs

Et le même exemple donne pareil :


In [21]:
x = "ab0cABC0abc123456abcABCabc99abcZZdeFG597abcZZdeFG597abcZZdeFG597abcZZdeFG597aethjrynghù*ejgodknùebjtzinhmodgkùjihrznhumbajzdgihbjmnaekrzùdbnvkzriùnodgkl ojzirnùodk bùgbznùod1249721325414765132486513486565465klfrzinhbùodfskl p*bjùdkl nbdnù"
y = "abZQXCVQDScD0EFd0ef123456abcDEFdef9999AbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQAbCdEFG413ZAQCWQzrthekĝbùpbgmhbgdmv hubznemr1249721325414765132486513486565465ebgd"
iDebut, jDebut, sousxy, longueurs = sousMotMaxGloutonCreux2(x, y)
print("Taille de la matrice pleine = (n+1)(m+1) =", (len(x) + 1) * (len(y) + 1))
print("Taille de la matrice creuse longueurs =", longueurs.size)
print("Sous-mot :", sousxy)


Taille de la matrice pleine = (n+1)(m+1) = 44215
Taille de la matrice creuse longueurs = 1046
Sous-mot : 1249721325414765132486513486565465

5. Calcule de la plus longue sous-séquence commune

Maintenant qu'on a fait tout ca, on peut implementer, de facon tres semblable, l'algorithme glouton pour le calcul de la plus longue sous-séquence commune.

Dans cet autre problème, on cherche des sous-séquences et plus des sous-mots, donc on peut extraire de facon non consécutives. Le développement d'agrégation devrait concerner le second problème, qui est plus intéressant: Par exemple, voici une version tapée en PDF : http://minerve.bretagne.ens-cachan.fr/images/Dvt_plsc.pdf.

5.1 Vérifier qu'une sous-séquence est une bonne sous-séquence

On commencer par écrire une petite fonction qui permet de vérifier rapidement qu'une chaine est une sous-séquence d'une autre, juste en regardant la définition.


In [22]:
def estSousSeq(seq, x, verb=True, indices=True):
    """ Verifie en temps O(|seq| |x|) que seq est une bonne sous-sequence de x.
    """
    result = False
    indices_x = []
    try:
        i = -1
        for l in seq:
            j = i+1 + x[i+1:].index(l)
            indices_x.append(j)
            i = j
        result = True
    except Exception as e:
        if verb:
            print("Erreur dans estSousSeq(seq = {}, x = {}):\n{}".format(seq, x, e))
    if indices:
        return result, indices_x
    else:
        return result

5.2 Algorithme pour la plus longue sous-séquence

On adapte l'algorithme du plus long sous-mot pour détecter les séquences aussi. Cf. le PDF page 2/3.

TODO meilleures explications


In [23]:
def utiliseTableOrigines_x(x, origines, i, j, accu=''):
    """ Renvoie la sous-séquence de x codée dans la table origines. Cf. PDF (Algorithme 2).
    
        - Calcul tail récursif (stocké dans la variable accu).
    """
    # print("  utiliseTableOrigines(x = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...".format(x, i, j, accu, origines[i, j]))  # DEBUG
    if i == 0 or j == 0:
        return accu
    if origines[i, j] == '↖':    # Vraie correspondance, on ajoute une lettre !
        return utiliseTableOrigines_x(x, origines, i-1, j-1, x[i-1] + accu)
    elif origines[i, j] == '↑':  # Fausse correspondance, on continue a gauche...
        return utiliseTableOrigines_x(x, origines, i-1, j, accu)
    elif origines[i, j] == '←':  # Fausse correspondance, on continue en haut...
        return utiliseTableOrigines_x(x, origines, i, j-1, accu)
    else:
        raise ValueError("Erreur dans la table 'origines', invalide pour le mot x = {} ...".format(x))


def utiliseTableOrigines_y(x, origines, i, j, accu=''):
    """ Renvoie la sous-séquence de y codée dans la table origines. Cf. PDF (Algorithme 2).
    
        - Calcul tail récursif (stocké dans la variable accu).
    """
    # print("  utiliseTableOrigines(y = {}, origines, i = {}, j = {}, accu = {}) : origines[i, j] = {} ...".format(y, i, j, accu, origines[i, j]))  # DEBUG
    if i == 0 or j == 0:
        return accu
    if origines[i, j] == '↖':    # Vraie correspondance, on ajoute une lettre !
        return utiliseTableOrigines_y(x, origines, i-1, j-1, y[j-1] + accu)
    elif origines[i, j] == '↑':  # Fausse correspondance, on continue a gauche...
        return utiliseTableOrigines_y(x, origines, i-1, j, accu)
    elif origines[i, j] == '←':  # Fausse correspondance, on continue en haut...
        return utiliseTableOrigines_y(x, origines, i, j-1, accu)
    else:
        raise ValueError("Erreur dans la table 'origines', invalide pour le mot y = {} ...".format(y))

TODO meilleures explications


In [24]:
def sousMotSeqGlouton(x, y, verb=False, verifie=True):
    """ Calcule la plus longue sous-mot séquence a x et y, par programmation dynamique.
    
        - affiche un peu ce qu'il se passe si verb=True,
        - vérifie que la sous-séquence commun est bien une bonne sous-séquence commune si verifie=True,
        - renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=False,
        - renvoie laSousSeq, longueurs, origines, indices_x, indices_y si verifie=True.
    """
    def message(*args):
        if verb:
            print(*args) 
    # 1. et 2. Initialisation et construction Matrice longueurs
    n = len(x)
    m = len(y)
    message("\n1. Initialisation des look-up matrices longueurs et origines de taille (n+1, m+1) : n = {} m = {} ...".format(n, m))
    longueurs = np.zeros((n+1, m+1), dtype=int)     # Matrice c du dev en PDF
    origines = np.array([[' '] * (m+1)] * (n+1), dtype=str)  # Matrice b du dev en PDF
    # Note : on pourrait utiliser un codage a base d'entier, 0 1 2 3 pour ' ' '←' '↑' '↖' mais c'est moins joli...
    message("2. Construction bottom-up des loop-up matrices longueurs et origines ...")
    for i in range(1, n+1):
        for j in range(1, m+1):
            if x[i-1] == y[j-1]:
                longueurs[i, j] = 1 + longueurs[i-1, j-1]
                origines[i, j] = '↖'
                message("      Vraie correspondance en cours, u[{}] = {} et v[{}] = {}, de longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))
            elif longueurs[i-1, j] >= longueurs[i, j-1]:
                longueurs[i, j] = longueurs[i-1, j]
                origines[i, j] = '↑'
                message("      Correspondance gauche (u) en cours, u[{}] = {} et v[{}] = {}, de pseudo-longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))
            else:
                longueurs[i, j] = longueurs[i, j-1]
                origines[i, j] = '←'
                message("      Correspondance haute (v) en cours, u[{}] = {} et v[{}] = {}, de pseudo-longueur courante {} ...".format(i-1, x[i-1], j-1, y[j-1], longueurs[i, j]))

    # 3. Utilisation de la matrice longueurs
    laSousSeq = utiliseTableOrigines_x(x, origines, n, m, accu='')

    # 4. Vérification
    if verifie:
        res_x, indices_x = estSousSeq(laSousSeq, x, indices=True)
        if not res_x:
            raise ValueError("Erreur: La séquence {} de x (aux indices {}) n'est pas une bonne sous-séquence de x = {}.".format(laSousSeq, indices_x, x))
        
        laSousSeq_y = utiliseTableOrigines_y(y, origines, n, m, accu='')
        if laSousSeq != laSousSeq_y:
            raise ValueError("Erreur: La sous-séquence {} de x est différente de celle de y : {} ...".format(laSousSeq, laSousSeq_y))

        res_y, indices_y = estSousSeq(laSousSeq, y, indices=True)
        if not res_y:
            raise ValueError("Erreur: La séquence {} de y (aux indices {}) n'est pas une bonne sous-séquence de y = {}.".format(laSousSeq, indices_y, y))
        
        # Fini !
        return laSousSeq, longueurs, origines, indices_x, indices_y
    else:
        return laSousSeq, longueurs, origines

5.2.1 Exemple, venant du développement

Blabla


In [25]:
x = "ABCBDAB"
y = "BDCABA"
laSousSeq, longueurs, origines, indices_x, indices_y = sousMotSeqGlouton(x, y, verifie=True)
print("Sous-seq de taille", len(laSousSeq), "valant", laSousSeq, "...")
print("   - aux indices", indices_x, "pour x =", x, "...")
print("   - aux indices", indices_y, "pour y =", y, "...")
print("Et la table longueurs vaut :\n", longueurs, "...")
print("Et la table origines vaut :\n", origines, "...")


Sous-seq de taille 4 valant BCBA ...
   - aux indices [1, 2, 3, 5] pour x = ABCBDAB ...
   - aux indices [0, 2, 4, 5] pour y = BDCABA ...
Et la table longueurs vaut :
 [[0 0 0 0 0 0 0]
 [0 0 0 0 1 1 1]
 [0 1 1 1 1 2 2]
 [0 1 1 2 2 2 2]
 [0 1 1 2 2 3 3]
 [0 1 2 2 2 3 3]
 [0 1 2 2 3 3 4]
 [0 1 2 2 3 4 4]] ...
Et la table origines vaut :
 [[' ' ' ' ' ' ' ' ' ' ' ' ' ']
 [' ' '↑' '↑' '↑' '↖' '←' '↖']
 [' ' '↖' '←' '←' '↑' '↖' '←']
 [' ' '↑' '↑' '↖' '←' '↑' '↑']
 [' ' '↖' '↑' '↑' '↑' '↖' '←']
 [' ' '↑' '↖' '↑' '↑' '↑' '↑']
 [' ' '↑' '↑' '↑' '↖' '↑' '↖']
 [' ' '↖' '↑' '↑' '↑' '↖' '↑']] ...

5.2.2 Autres exemples

TODO


C'est tout pour aujourd'hui les amis ! Allez voir d'autres notebooks si vous voulez.